package leet46permutations

func permute(nums []int) [][]int {
	var res [][]int
	var path []int
	var backtrack func(used []bool)
	// used表示在整个上文的递归栈中是否已经使用过某个元素
	backtrack = func(used []bool) {
		if len(path) == len(nums) {
			// 复制一份结果
			result := make([]int, len(path))
			copy(result, path)
			res = append(res, result)
			return
		}
		for i := 0; i < len(nums); i++ {
			// 这个used简直是太棒了，避免了重复使用同一个元素
			if used[i] {
				continue
			}
			used[i] = true
			path = append(path, nums[i])
			backtrack(used)
			// 回溯
			used[i] = false
			path = path[:len(path)-1]
		}
	}
	backtrack(make([]bool, len(nums)))
	return res
}
